package com.ljy.kotlindemo.leetcode

import android.annotation.SuppressLint
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap
import kotlin.collections.HashSet
import kotlin.math.abs
import kotlin.math.min
import kotlin.String as String


/**
 * @Author:         LiuJinYang
 * @CreateDate:     2020/11/9
 */


/**
 * 1. 两数之和
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
 */
fun _0001_twoSum1() {
    println("--------_001_twoSum-------")
    val nums = intArrayOf(1, 2, 11, 7, 15)
    println("_001_AddTwoNumber-->")
    for (i in twoSum1(nums, 9)!!) {
        println(i)
    }
}

/**
 * 这道 Two Sum 的题目作为 LeetCode 的开篇之题，乃是经典中的经典，正所谓‘ 平生不识 TwoSum，刷尽 LeetCode 也枉然
 */
fun twoSum1(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    for (i in nums.indices) {
        if (map.containsKey(target - nums[i])) {
            return intArrayOf(map[target - nums[i]]!!, i)
        }
        map[nums[i]] = i
    }
    return intArrayOf()
}

/**
 * 2. 两数相加
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
 */
fun _0002_addTwoNumbers() {
    println("--------_002_addTwoNumbers-------")
    addTwoNumbers(
        ListNode1(2, ListNode1(4, ListNode1(3))),
        ListNode1(5, ListNode1(6, ListNode1(4)))
    )?.print()
    println()
    addTwoNumbers(
        ListNode1(2, ListNode1(4, ListNode1(3, ListNode1(1)))),
        ListNode1(5, ListNode1(6, ListNode1(4, ListNode1(5))))
    )?.print()
    println()
}


/**
 * 建立一个新链表，然后把输入的两个链表从头往后撸，每两个相加，添加一个新节点到新链表后面。
 * 为了避免两个输入链表同时为空，我们建立一个 dummy 结点，将两个结点相加生成的新结点按顺序加到 dummy 结点之后，
 * 由于 dummy 结点本身不能变，所以用一个cur 来指向新链表的最后一个结点。
 */
fun addTwoNumbers(l1: ListNode1?, l2: ListNode1?): ListNode1? {
    var l1 = l1
    var l2 = l2
    val dummy = ListNode1(-1)
    var cur: ListNode1? = dummy
    var carry = 0
    while (l1 != null || l2 != null) {
        val d1 = l1?.data ?: 0
        val d2 = l2?.data ?: 0
        val sum = d1 + d2 + carry
        carry = if (sum >= 10) 1 else 0
        cur?.next = ListNode1(sum % 10)
        cur = cur?.next
        if (l1 != null) {
            l1 = l1.next
        }
        if (l2 != null) {
            l2 = l2.next
        }
    }
    if (carry == 1) cur?.next = ListNode1(1)
    return dummy.next
}

 class ListNode1 {
    var data = 0
    var next: ListNode1? = null

    internal constructor(data: Int) {
        this.data = data
    }

    internal constructor(data: Int, next: ListNode1?) {
        this.data = data
        this.next = next
    }

    fun print() {
        print("-->$data")
        if (next != null) {
            next?.print()
        } else {
            println()
        }

    }
}

/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */
fun _0003_lengthOfLongestSubstring1() {
    println("--------_003_lengthOfLongestSubstring-------")
    lengthOfLongestSubstring1("abcabcbb")
    lengthOfLongestSubstring1("bbbbb")
    lengthOfLongestSubstring1("pwwkew")
    lengthOfLongestSubstring1("pwwkewabcdefghijkabcabc")
}

/**
 * 使用了 HashSet，把出现过的字符都放入 HashSet 中，遇到 HashSet 中没有的字符就加入 HashSet 中
 * 并更新结果 res，如果遇到重复的，则从左边开始删字符，直到删到重复的字符停止：
 */
fun lengthOfLongestSubstring1(s: String) {
    var maxLen = 0
    var left = 0
    var right = 0
    val temp = HashSet<Char>()
    while (right < s.length) {
        if (!temp.contains(s[right])) {
            temp.add(s[right++])
            maxLen = Math.max(maxLen, temp.size)
        } else {
            temp.remove(s[left++])
        }
    }
    println("len：$maxLen")
}

/**
 * 4. 寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
 */
fun _0004_findMedianSortedArrays() {
    println("--------_004_findMedianSortedArrays-------")
    println(findMedianSortedArrays(intArrayOf(1, 3), intArrayOf(2)))
    println(findMedianSortedArrays(intArrayOf(1, 2), intArrayOf(3, 4)))
    println(findMedianSortedArrays(intArrayOf(0, 0), intArrayOf(0, 0)))
    println(findMedianSortedArrays(intArrayOf(), intArrayOf(1)))
    println(findMedianSortedArrays(intArrayOf(2), intArrayOf()))
    println(findMedianSortedArrays(intArrayOf(1, 2, 3, 4, 5), intArrayOf(3, 4, 5, 6)))
}

/**
 * 用迭代形式的二分搜索法来解，是所谓的中位数，换一种角度去看，其实就是把一个有序数组分为长度相等的两段，
 * 中位数就是前半段的最大值和后半段的最小值的平均数，也就是离分割点相邻的两个数字的平均值。
 * 比如说对于偶数个数组 [1 3 5 7]，那么分割开来就是 [1 3 / 5 7]，其中 '/' 表示分割点，中位数就是3和5的平均值。
 * 对于奇数个数组 [1 3 4 5 7]，可以分割为 [1 3 4 / 4 5 7]，可以发现左右两边都有个4，则中位数是两个4的平均数，还是4。
 */
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    var m = nums1.size
    var n = nums2.size
    if (m < n) return findMedianSortedArrays(nums2, nums1)
    if (n == 0) {
        return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0
    }
    var left = 0
    var right = 2 * n
    while (left <= right) {
        var mid2 = (left + right) / 2
        var mid1 = m + n - mid2
        var l1: Double = if (mid1 == 0) Double.MIN_VALUE else nums1[(mid1 - 1) / 2].toDouble()
        var l2: Double = if (mid2 == 0) Double.MIN_VALUE else nums2[(mid2 - 1) / 2].toDouble()
        var r1: Double = if (mid1 == m * 2) Double.MAX_VALUE else nums1[mid1 / 2].toDouble()
        var r2: Double = if (mid2 == n * 2) Double.MAX_VALUE else nums2[mid2 / 2].toDouble()
        if (l1 > r2) left = mid2 + 1
        else if (l2 > r1) right = mid2 - 1
        else return (Math.max(l1, l2) + Math.min(r1, r2)) / 2
    }
    return -1.0
}

/**
 * 5. 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
 */
fun _0005_longestPalindrome() {
    println("--------_005_longestPalindrome-------")
    println(longestPalindrome("babad"))
    println(longestPalindrome("cbbd"))
    println(longestPalindrome("aaaadcbabcdfabcccccc"))
}

/**
 * 马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法，
 * 由一个叫Manacher的人在1975年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性。
 */
fun longestPalindrome(s: String): String? {
    if (s.length < 2) {
        return s
    }
    var temp = "$"
    for (element in s) {
        temp += "#$element"
    }
    temp += "#@"
    val n = temp.length
    val p = IntArray(n)
    var id = 0
    var mx = 0
    var index = 0
    var maxLen = -1
    for (i in 1 until n - 1) {
        p[i] = if (mx > i) Math.min(p[2 * id - i], mx - i) else 1
        while (temp[i + p[i]] == temp[i - p[i]]) {
            p[i]++
        }
        if (mx < i + p[i]) {
            mx = i + p[i]
            id = i
        }
        if (maxLen < p[i] - 1) {
            maxLen = p[i] - 1
            index = i
        }
    }
    val start = (index - maxLen) / 2
    return s.substring(start, start + maxLen)
}

/**
 * 6. Z 字形变换
 * 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L   C   I   R
E T O E S I I G
E   D   H   N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L     D     R
E   O E   I I
E C   I H   N
T     S     G
 */
fun _0006_convert() {
    println("--------_006_convert-------")
    println(convert("LEETCODEISHIRING", 3))
    println(convert("LEETCODEISHIRING", 4))
}

fun convert(s: String, numRows: Int): String {
    var convert = ""
    val len = s.length
    if (numRows <= 1) return s
    val door = 2 * numRows - 2

    for (i in 0 until numRows) {
        for (j in i until len step door) {
            val k = j + door - 2 * i
            convert += s[j]
            if (i != 0 && i != numRows - 1 && k < len) {
                convert += s[k]
            }
        }
    }
    return convert
}


/**
 * 7. 整数反转
 * 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
 示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
 */
fun _0007_reverse() {
    println("--------_007_reverse-------")
    println(reverse(123))
    println(reverse(-123))
    println(reverse(120))
    println(reverse(980))
    println(reverse(Int.MAX_VALUE))
    println(reverse(Int.MIN_VALUE))
    println(Math.pow(2.0, 31.0))
    println(Int.MIN_VALUE)
}

fun reverse(x: Int): Int {
    var x = x
    var res: Int = 0
    while (x != 0) {
        if (abs(res) > Int.MAX_VALUE / 10) return 0
        res = res * 10 + x % 10
        x /= 10
    }
    return res
}

/**
 * 8. 字符串转换整数 (atoi)
 * 请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
     因此返回 INT_MIN (−231) 。
 */

fun _0008_myAtoi() {
    println("--------_008_myAtoi-------")
    println(myAtoi("42"))
    println(myAtoi("   -42"))
    println(myAtoi("4193 with words"))
    println(myAtoi("words and 987"))
    println(myAtoi("-91283472332"))
}


fun myAtoi(s: String): Int {
    if (s.isEmpty()) return 0
    var sign = 1
    var base = 0
    var i = 0
    val n = s.length
    while (i < n && s[i] == ' ') ++i
    if (i < n && (s[i] == '+' || s[i] == '-')) {
        sign = if (s[i++] == '+') 1 else -1
    }
    while (i < n && s[i] >= '0' && s[i] <= '9') {
        if (base > Int.MAX_VALUE / 10 || (base == Int.MAX_VALUE / 10 && s[i] - '0' > 7)) {
            return if (sign == 1) Int.MAX_VALUE else Int.MIN_VALUE
        }
        base = 10 * base + (s[i++] - '0')
    }
    return base * sign
}

/**
 * 9. 回文数
 * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
 */
fun _0009_isPalindrome() {
    println("--------_009_isPalindrome-------")
    println(isPalindrome(121))
    println(isPalindrome(-121))
    println(isPalindrome(10))
    println(isPalindrome(222))
    println(isPalindrome(10101))
}

/**
 * 首先判断x是否为负数，这里可以用一个小 trick，因为整数的最高位不能是0，所以回文数的最低位也不能为0，数字0除外，
 * 所以如果发现某个正数的末尾是0了，也直接返回 false 即可。
 * 好，下面来看具体解法，要验证回文数，那么就需要看前后半段是否对称，如果把后半段翻转一下，就看和前半段是否相等就行了。
 * 所以做法就是取出后半段数字，进行翻转，具体做法是，每次通过对 10 取余，取出最低位的数字，然后加到取出数的末尾，
 * 就是将 revertNum 乘以 10，再加上这个余数，这样翻转也就同时完成了，每取一个最低位数字，x都要自除以 10。
 * 这样当 revertNum 大于等于x的时候循环停止。由于回文数的位数可奇可偶，如果是偶数的话，那么 revertNum 就应该和x相等了；
 * 如果是奇数的话，那么最中间的数字就在 revertNum 的最低位上了，除以 10 以后应该和x是相等的
 */
fun isPalindrome(x: Int): Boolean {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false
    var x = x
    var revertNum = 0
    while (x > revertNum) {
        revertNum = revertNum * 10 + x % 10
        x /= 10
    }
    return x == revertNum || x == revertNum / 10
}

/**
 * 10. 正则表达式匹配
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4：
输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5：
输入：s = "mississippi" p = "mis*is*p*."
输出：false
提示：
0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符
 */
fun _0010_isMatch() {
    println("--------_010_isMatch-------")
    println(isMatch("aa", "a"))
    println(isMatch("aa", "a*"))
    println(isMatch("ab", ".*"))
    println(isMatch("aab", "c*a*b"))
    println(isMatch("mississippi", "mis*is*p*."))
}

/**
 * 先来判断p是否为空，若为空则根据s的为空的情况返回结果。
 * 当p的第二个字符为*号时，由于*号前面的字符的个数可以任意，可以为0，那么我们先用递归来调用为0的情况，
 * 就是直接把这两个字符去掉再比较，或者当s不为空，且第一个字符和p的第一个字符相同时，再对去掉首字符的s和p调用递归，
 * 注意p不能去掉首字符，因为号前面的字符可以有无限个；如果第二个字符不为号，那么就老老实实的比较第一个字符，
 * 然后对后面的字符串调用递归
 */
fun isMatch(s: String, p: String): Boolean {
    if (p.isEmpty()) return s.isEmpty()
    return if (p.length > 1 && p[1] == '*') {
        isMatch(s, p.substring(2)) || (s.isNotEmpty() && (s[0] == p[0] || p[0] == '.') && isMatch(
            s.substring(
                1
            ), p
        ))
    } else {
        s.isNotEmpty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substring(1), p.substring(1))
    }
}

/**
 * 11. 盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器
示例 1：
输入：height =[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
提示：
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104
 */
fun _0011_maxArea() {
    println("--------_011_maxArea-------")
    println(maxArea(intArrayOf(1, 8, 6, 2, 5, 4, 8, 3, 7)))
    println(maxArea(intArrayOf(1, 1)))
    println(maxArea(intArrayOf(4, 3, 2, 1, 4)))
    println(maxArea(intArrayOf(1, 2, 1)))
    println(maxArea(intArrayOf(4, 3, 9, 1, 1, 9, 2, 1)))
}

/**
 * 定义i和j两个变量分别指向数组的左右两端，然后两个指针向中间搜索，每移动一次算一个值和结果比较取较大的，
 * 容器装水量的算法是找出左右两个边缘中较小的那个乘以两边缘的距离，
 * 对于相同的高度们直接移动i和j就行了，不再进行计算容量了
 */
fun maxArea(height: IntArray): Int {
    var res = 0
    var i = 0
    var j = height.size - 1
    while (i < j) {
        val h = Math.min(height[i], height[j])
        res = Math.max(res, h * (j - i))
        while (i < j && h == height[i]) ++i
        while (i < j && h == height[j]) --j
    }
    return res
}

/**
 * 12. 整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，
所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:
输入: 3
输出: "III"
示例 2:
输入: 4
输出: "IV"
示例 3:
输入: 9
输出: "IX"
示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
 */
fun _0012_intToRoman() {
    println("--------_012_intToRoman-------")
    println(intToRoman(3))
    println(intToRoman(4))
    println(intToRoman(9))
    println(intToRoman(58))
    println(intToRoman(49))
    println(intToRoman(444))
    println(intToRoman(555))
    println(intToRoman(666))
    println(intToRoman(888))
    println(intToRoman(999))
    println(intToRoman(1994))
    println(intToRoman(3999))
}

/**
 * 本题由于限制了输入数字范围这一特殊性，故而有一种利用贪婪算法的解法，
 * 建立一个数表，每次通过查表找出当前最大的数，减去再继续查表
 */
fun intToRoman(num: Int): String {
    print("$num-->")
    var num = num
    val strs = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
    val nums = intArrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
    val result = StringBuffer()
    for (i in nums.indices) {
        while (num >= nums[i]) {
            num -= nums[i]
            result.append(strs[i])
        }
    }
    return result.toString()
}

/**
 * 13. 罗马数字转整数
 * 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，
所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示：
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IC 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
 */
fun _0013_romanToInt() {
    println("--------_013_romanToInt-------")
    println(romanToInt("III"))
    println(romanToInt("IV"))
    println(romanToInt("IX"))
    println(romanToInt("LVIII"))
    println(romanToInt("XLIX"))
    println(romanToInt("CDXLIV"))
    println(romanToInt("DLV"))
    println(romanToInt("DCLXVI"))
    println(romanToInt("DCCCLXXXVIII"))
    println(romanToInt("CMXCIX"))
    println(romanToInt("MCMXCIV"))
    println(romanToInt("MMMCMXCIX"))

}

/**
需要用到 HashMap 数据结构，来将罗马数字的字母转化为对应的整数值，因为输入的一定是罗马数字，
那么只要考虑两种情况即可：
第一，如果当前数字是最后一个数字，或者之后的数字比它小的话，则加上当前数字。
第二，其他情况则减去这个数字。
 */
fun romanToInt(s: String): Int {
    print("$s-->")
    var s = s
    var res = 0
    val map = mapOf('I' to 1, 'V' to 5, 'X' to 10, 'L' to 50, 'C' to 100, 'D' to 500, 'M' to 1000)
    for (i in s.indices) {
        val t: Int = map.getValue(s[i])
        if (i == s.length - 1 || map.getValue(s[i + 1]) <= map.getValue(s[i])) res += t
        else res -= t
    }
    return res
}

/**
 * 14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
 */
fun _0014_longestCommonPrefix() {
    println("--------_014_longestCommonPrefix-------")
    println(longestCommonPrefix(arrayOf("flower", "flow", "flight")))
    println(longestCommonPrefix(arrayOf("dog", "racecar", "car")))
}

/**
 * 给输入字符串数组排个序，按字母顺序排序的话，那么有共同字母多的两个字符串会被排到一起，
 * 而跟大家相同的字母越少的字符串会被挤到首尾两端，那么如果有共同前缀的话，一定会出现在首尾两端的字符串中，
 * 所以只需要找首尾字母串的共同前缀即可。
 * 由于是按字母顺序排的，而不是按长度，所以首尾字母的长度关系不知道，为了防止溢出错误，只遍历而这种较短的那个的长度，
 * 找出共同前缀返回即可
 */
fun longestCommonPrefix(strs: Array<String>?): String {
    if (strs == null || strs.isEmpty()) return ""
    Arrays.sort(strs)
    var i = 0
    var len = min(strs[0].length, strs[strs.size - 1].length)
    while (i < len && strs[0][i] == strs[strs.size - 1][i]) {
        i++
    }
    return strs[0].substring(0, i)
}

/**
 * 15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -1,1,-4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
 */
fun _0015_threeSum() {
    println("--------_015_threeSum-------")
    println(threeSum(intArrayOf(-1, 0, 1, -2, 2, 2, -1, -1, 1, -4)).toString())
}

fun threeSum(nums: IntArray?): List<List<Int>> {
    if (nums == null || nums.size < 3) return ArrayList()
    Arrays.sort(nums)
    val ret = LinkedList<List<Int>>()
    val set = HashSet<List<Int>>()
    for (i in 0..nums.size - 2) {
        if (i > 0 && nums[i] == nums[i - 1]) continue//对i去重
        var start = i + 1
        var end = nums.size - 1
        while (start < end) {
            if (nums[i] + nums[start] + nums[end] == 0) {
                val oneResult = LinkedList<Int>()
                oneResult.add(nums[i])
                oneResult.add(nums[start])
                oneResult.add(nums[end])
                set.add(oneResult)
                start++
                end--
            } else {
                if (nums[i] + nums[start] + nums[end] < 0) {
                    start++
                } else {
                    end--
                }
            }
        }
    }
    ret.addAll(set)
    return ret

}

/**
 * 16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。
返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
 */
fun _0016_threeSumClosest() {
    println("--------_0016_threeSumClosest-------")
    println(threeSumClosest(intArrayOf(-1, 2, 1, -4), 1))
    println(threeSumClosest(intArrayOf(-1, -2, 2, 1, -4), 1))
    println(threeSumClosest(intArrayOf(2, 1, -4), 1))
}

fun threeSumClosest(nums: IntArray?, target: Int): Int {
    if (nums == null || nums.size < 3) return 0
    var result = nums[0] + nums[1] + nums[2]
    Arrays.sort(nums)
    for (i in 0..nums.size - 2) {
        var start = i + 1
        var end = nums.size - 1
        while (start < end) {
            val sum = nums[i] + nums[start] + nums[end]
            if (sum > target) {
                end--
            } else {
                start++
            }
            if (abs(sum - target) < abs(result - target)) {
                result = sum
            }
        }
    }
    return result
}

/**
 *17. 电话号码的字母组合(九宫格键盘)
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 */
fun _0017_letterCombinations() {
    println("--------_0017_letterCombinations-------")
    println(letterCombinations("23"))
    println(letterCombinations("13"))
    println(letterCombinations("333"))
}

/**
 * 在遍历 digits 中所有的数字时，先建立一个临时的字符串数组t，通过数字到 dict 中取出字符串 str，
 * 然后遍历取出字符串中的所有字符，再遍历当前结果 res 中的每一个字符串，将字符加到后面，并加入到临时字符串数组t中。
 * 取出的字符串 str 遍历完成后，将临时字符串数组赋值给结果 res，具体实现参见代码如下：
 */
fun letterCombinations(digits: String?): ArrayList<String> {
    if (digits == null || digits.isEmpty()) return ArrayList()
    val dict = arrayListOf("0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
    var res = arrayListOf("")
    for (i in digits.indices) {
        val t = ArrayList<String>()
        val str = dict[digits[i] - '0']
        for (j in str.indices) {
            for (s in res) {
                t.add(s + str[j])
            }
        }
        res = t
    }
    return res
}

/**
 * 18. 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，
使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
 */
fun _0018_fourSum() {
    println("--------_0018_fourSum-------")
    println(fourSum(intArrayOf(1, 0, -1, 0, -2, 2), 0))
}

fun fourSum(nums: IntArray?, target: Int): List<List<Int>> {
    if (nums == null || nums.size < 4) return ArrayList()
    val res = ArrayList<List<Int>>()
    val n = nums.size
    Arrays.sort(nums)
    for (i in 0..n - 3) {
        if (i > 0 && nums[i] == nums[i - 1]) continue
        for (j in i + 1..n - 2) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue
            var left = j + 1
            var right = n - 1
            while (left < right) {
                val sum = nums[i] + nums[j] + nums[left] + nums[right]
                if (sum == target) {
                    val oneResult = arrayListOf(nums[i], nums[j], nums[left], nums[right])
                    res.add(oneResult)
                    while (left < right && nums[left] == nums[left + 1]) left++
                    while (left < right && nums[right] == nums[right - 1]) right--
                    left++
                    right--
                } else if (sum < target) {
                    left++
                } else right--
            }
        }
    }
    return res
}

/**
 * 19. 删除链表的倒数第N个节点
 *给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗
 */
fun _0019_removeNthFromEnd() {
    println("--------_0019_removeNthFromEnd-------")
    removeNthFromEnd(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5))))), 1)?.print()
    removeNthFromEnd(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5))))), 2)?.print()
    removeNthFromEnd(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5))))), 3)?.print()
    removeNthFromEnd(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5))))), 4)?.print()
    removeNthFromEnd(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5))))), 5)?.print()

}

/**
 * 这道题让我们移除链表倒数第N个节点，限定n一定是有效的，即n不会大于链表中的元素总数。
 * 还有题目要求一次遍历解决问题，那么就得想些比较巧妙的方法了。比如首先要考虑的时，如何找到倒数第N个节点，
 * 由于只允许一次遍历，所以不能用一次完整的遍历来统计链表中元素的个数，而是遍历到对应位置就应该移除了。
 * 那么就需要用两个指针来帮助解题，pre 和 cur 指针。首先 cur 指针先向前走N步，如果此时 cur 指向空，
 * 说明N为链表的长度，则需要移除的为首元素，那么此时返回 head->next 即可，如果 cur 存在，再继续往下走，
 * 此时 pre 指针也跟着走，直到 cur 为最后一个元素时停止，此时 pre 指向要移除元素的前一个元素，
 * 再修改指针跳过需要移除的元素即可
 */
fun removeNthFromEnd(head: ListNode1?, n: Int): ListNode1? {
    if (head?.next == null) return null
    var n = n
    var pre = head
    var cur = head
    for (i in 0 until n) {
        cur = cur?.next
    }
    if (cur == null) return head.next //说明n为链表长度
    while (cur?.next != null) {
        cur = cur.next
        pre = pre?.next
    }
    pre?.next = pre?.next?.next
    return head
}

/**
 * 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
 */
fun _0020_isValid() {
    println("--------_0020_isValid-------")
    println(isValid("()"))
    println(isValid("()[]{}"))
    println(isValid("(]"))
    println(isValid("{[]}"))
}

/**
 * 这里需要用一个栈，开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，
 * 若此时栈为空，则直接返回 false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回 false，代码如下：
 */
fun isValid(s: String): Boolean {
    val stack = Stack<Char>()
    for (i in s.indices) {
        val c = s[i]
        if (c == '(' || c == '{' || c == '[')
            stack.push(c)
        else {
            if (stack.isEmpty()) return false
            if (c == ')' && stack.peek() != '(') return false
            if (c == ']' && stack.peek() != '[') return false
            if (c == '}' && stack.peek() != '{') return false
            stack.pop()
        }
    }
    return stack.isEmpty()
}

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
 */
fun _0021_mergeTwoLists1() {
    println("--------_0021_mergeTwoLists-------")
    mergeTwoLists1(
        ListNode1(1, ListNode1(2, ListNode1(4))),
        ListNode1(1, ListNode1(3, ListNode1(4)))
    )?.print()
}

/**
 * 递归写法，当某个链表为空了，就返回另一个。然后核心还是比较当前两个节点值大小，如果 l1 的小，
 * 那么对于 l1 的下一个节点和 l2 调用递归函数，将返回值赋值给 l1.next，然后返回 l1；
 * 否则就对于 l2 的下一个节点和 l1 调用递归函数，将返回值赋值给 l2.next，然后返回 l2
 */
fun mergeTwoLists1(l1: ListNode1?, l2: ListNode1?): ListNode1? {
    if (l1 == null) return l2
    if (l2 == null) return l1
    return if (l1.data < l2.data) {
        l1.next = mergeTwoLists1(l1.next, l2);l1
    } else {
        l2.next = mergeTwoLists1(l1, l2.next);l2
    }
}

/**
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
 */
fun _0022_generateParenthesis() {
    println("--------_0022_generateParenthesis-------")
    println(generateParenthesis(1))
    println(generateParenthesis(2))
    println(generateParenthesis(3))
    println(generateParenthesis(4))
}

/**
 * 思想是找左括号，每找到一个左括号，就在其后面加一个完整的括号，最后再在开头加一个 ()，就形成了所有的情况，
 * 需要注意的是，有时候会出现重复的情况，所以用set数据结构，好处是如果遇到重复项，不会加入到结果中，
 * 最后我们再把set转为vector即可
 */
fun generateParenthesis(n: Int): List<String> {
    val res = HashSet<String>()
    if (n == 0) {
        res.add("")
    } else {
        val pre = generateParenthesis(n - 1)
        for (str in pre) {
            var str = str
            for (i in str.indices) {
                if (str[i] == '(') {
                    str = str.substring(0, i + 1) + "()" + str.substring(i + 1, str.length)
                    res.add(str)
                    str = str.substring(0, i + 1) + str.substring(i + 3, str.length)
                }
            }
            res.add("()$str")
        }
    }
    return res.toList()
}

/**
 * 23. 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
 */
fun _0023_mergeKLists() {
    println("--------_0023_mergeKLists-------")
    mergeKLists(
        arrayOf(
            ListNode1(1, ListNode1(4, ListNode1(5))),
            ListNode1(1, ListNode1(3, ListNode1(4))),
            ListNode1(2, ListNode1(6)),
        )
    )?.print()
    mergeKLists(arrayOf())?.print()
}

fun mergeKLists(list1s: Array<ListNode1?>): ListNode1? {
    val len = list1s.size
    if (len == 0) return null
    else if (len == 1) return list1s[0]
    var min: ListNode1? = null
    val prev = ListNode1(0)
    var head: ListNode1? = prev
    while (true) {
        var id = -1
        for (i in 0 until len) {
            if (min == null && list1s[i] != null) {
                min = list1s[i]
            }
            val curr = list1s[i]
            if (curr != null && curr.data <= min?.data!!) {
                min = curr
                id = i
            }
        }
        if (id != -1) {
            head?.next = min
            head = head?.next
            min = null
            list1s[id] = list1s[id]?.next
        } else break
    }
    return prev.next
}

/**
 * 24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
 */
fun _0024_swapPairs() {
    println("--------_0024_swapPairs-------")
    swapPairs(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5, ListNode1(6)))))))?.print()
    swapPairs(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4)))))?.print()
    swapPairs(ListNode1(1, ListNode1(2, ListNode1(3))))?.print()
    swapPairs(ListNode1(1))?.print()
}

/**
 * 利用了回溯的思想，递归遍历到链表末尾，然后先交换末尾两个，然后依次往前交换：
 */
fun swapPairs(head: ListNode1?): ListNode1? {
    if (head?.next == null) {
        return head
    }
    var temp = head.next
    head.next = swapPairs(head.next?.next)
    temp?.next = head
    return temp
}

/**
 * 25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
fun _0025_reverseKGroup1() {
    println("--------_0025_reverseKGroup-------")
    reverseKGroup1(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5))))), 2)?.print()
    reverseKGroup1(ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5))))), 3)?.print()
    reverseKGroup1(
        ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5, ListNode1(6)))))),
        2
    )?.print()
    reverseKGroup1(
        ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5, ListNode1(6)))))),
        3
    )?.print()
    reverseKGroup1(
        ListNode1(1, ListNode1(2, ListNode1(3, ListNode1(4, ListNode1(5, ListNode1(6)))))),
        4
    )?.print()
}

/**
 * 首先遍历整个链表，统计出链表的长度，然后如果长度大于等于k，交换节点，当 k=2 时，每段只需要交换一次，
 * 当 k=3 时，每段需要交换2此，所以i从1开始循环，注意交换一段后更新 pre 指针，然后 num 自减k，
 * 直到 num<k 时循环结束
 */
fun reverseKGroup1(head: ListNode1?, k: Int): ListNode1? {
    var dummy = ListNode1(-1)
    var pre: ListNode1? = dummy
    var cur: ListNode1? = pre
    dummy.next = head
    var num = 0
    while (cur?.next != null) {
        cur = cur.next
        ++num
    }
    while (num >= k) {
        cur = pre?.next
        for (i in 1 until k) {
            var temp = cur?.next
            cur?.next = temp?.next
            temp?.next = pre?.next
            pre?.next = temp
        }
        pre = cur
        num -= k
    }
    return dummy.next
}

/**
 * 26. 删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 */
fun _0026_removeDuplicates() {
    println("--------_0026_removeDuplicates-------")
    println(removeDuplicates(intArrayOf(1, 1, 2)))
    println(removeDuplicates(intArrayOf(0, 0, 1, 1, 1, 2, 2, 3, 3, 4)))
}

/**
 * 用变量i表示当前覆盖到到位置，由于不能有重复数字，则只需要用当前数字 num 跟上一个覆盖到的
 * 数字 nums[i-1] 做个比较，只要 num 大，则一定不会有重复（前提是数组必须有序）
 */
fun removeDuplicates(nums: IntArray): Int {
    var i = 0
    for (num in nums) {
        if (i < 1 || num > nums[i - 1]) {
            nums[i++] = num
        }
    }
    return i
}

/**
 * 27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 */
fun _0027_removeElement() {
    println("--------_0027_removeElement-------")
    println(removeElement(intArrayOf(3, 2, 2, 3), 3))
    println(removeElement(intArrayOf(0, 1, 2, 2, 3, 0, 4, 2), 2))
}

/**
 * 只需要一个变量用来计数，然后遍历原数组，如果当前的值和给定值不同，就把当前值覆盖计数变量的位置，并将计数变量加1
 */
fun removeElement(nums: IntArray, k: Int): Int {
    var res = 0
    for (i in nums.indices) {
        if (nums[i] != k) {
            nums[res++] = nums[i]
        }
    }
    return res
}

/**
 * 28. 实现 strStr()函数
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 */
fun _0028_strStr() {
    println("--------_0028_strStr-------")
    println(strStr("hello", "ll"))
    println(strStr("hello", "o"))
    println(strStr("hello", "he"))
    println(strStr("aaaaa", "bba"))
}

/**
 * 开头直接套两个 for 循环，不写终止条件，然后判断假如j到达 needle 的末尾了，此时返回i；
 * 若此时 i+j 到达 haystack 的长度了，返回 -1；否则若当前对应的字符不匹配，直接跳出当前循环
 */
fun strStr(haystack: String, needle: String): Int {
    var i = 0
    var j = 0
    while (i >= 0) {
        while (j >= 0) {
            if (j == needle.length) return i
            if (i + j == haystack.length) return -1
            if (needle[j] != haystack[i + j]) break
            j++
        }
        i++
    }
    return -1
}

/**
 * 29. 两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
 */
fun _0029_divide() {
    println("--------_0029_divide-------")
    println(divide(10, 3))
    println(divide(7, -3))
}

/**
 * 通过递归的方法来解
 * kotlin常用的7种中缀表达式
var a = 5,b = 11
and  对应位都为1，则为1，如：a and b= 001 => 1
or     对应位有一个是1，则为1 如：a or b= 111 => 7
xor   对应位值相同，则结果为0，否则为1 如：a xor b= 110 => 6
inv   对应位取相反的值，如： a.inv() => 1010 =>1001 => 1110 => -110 =>-6
shl   按位左移指定的位数，相当于乘以2的N次方。移掉的省略，右边缺失的位，用0补齐
shr   按位右移指定的位数，相当于除以2的N次方，移掉的省略，左边缺失的位，如果是正数则补0，若为负数，可能补0或补1，这取决于所用的计算机系统
ushr 按位右移指定的位数，移掉的省略，左边缺失的位，用0补齐
 */
fun divide(dividend: Int, divisor: Int): Int {
    val m = abs(dividend)
    val n = abs(divisor)
    var res = 0
    if (m < n) return 0
    var t = n
    var p = 1
    while (m > (t shl 1)) {
        t = t shl 1
        p = p shl 1
    }
    res += p + divide(m - t, n)
    if ((dividend < 0) xor (divisor < 0)) res = -res
    return if (res > Int.MAX_VALUE) Int.MAX_VALUE else res
}

/**
 * 30. 串联所有单词的子串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
 */
fun _0030_findSubstring() {
    println("--------_0030_findSubstring-------")
    println(findSubstring("barfoothefoobarman", arrayOf("foo", "bar")))
    println(findSubstring("wordgoodgoodgoodbestword", arrayOf("word", "good", "best", "word")))
    println(findSubstring("findsubstring", arrayOf("sub", "str")))
}

/**
 * 把 words 数组中的所有单词放入 HashMap ，同时统计每个单词的出现次数。借助 HashMap 快速查找的特点，来匹配 s 字符串。
 * 整体的思路很简单明了，就是挨个匹配。
 */
@SuppressLint("NewApi")
fun findSubstring(s: String, words: Array<String>): List<Int> {
    val result = ArrayList<Int>()
    if (s.isEmpty() || words.isEmpty()) return result
    val countMap = HashMap<String, Int>()
    for (i in words.indices) {
        countMap.put(words[i], countMap.getOrDefault(words[i], 0) + 1);
    }
    val wordLen = words[0].length
    val wordsLen = words.size * wordLen
    for (i in 0..s.length - wordsLen) {
        val workMap: MutableMap<String, Int> = HashMap()
        var j = 0
        while (j < words.size) {
            val word = s.substring(i + j * wordLen, i + (j + 1) * wordLen)
            workMap[word] = workMap.getOrDefault(word, 0) + 1
            if (workMap[word]!! > countMap.getOrDefault(word, 0)) break // 匹配失败
            ++j
        }
        if (j == words.size) result.add(i)
    }
    return result
}

/**
 * 31. 下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
 */
fun _0031_nextPermutation() {
    println("--------_0031_nextPermutation-------")
    nextPermutation(intArrayOf(1, 2, 3))
    nextPermutation(intArrayOf(3, 2, 1))
    nextPermutation(intArrayOf(1, 1, 5))
    nextPermutation(intArrayOf(1))
}

fun nextPermutation(nums: IntArray) {
    val n = nums.size;
    var i = n - 2;
    var j = n - 1
    while (i >= 0 && nums[i] >= nums[i + 1]) --i
    if (i >= 0) {
        while (nums[j] <= nums[i]) --j
        swap(i, j, nums)
    }
    reverse(nums, i + 1)

    println(nums.contentToString())
}

private fun reverse(nums: IntArray, index: Int) {
    var i = index
    var j = nums.size - 1
    while (i < j) {
        swap(i, j, nums)
        i++
        j--
    }
}

private fun swap(i: Int, j: Int, nums: IntArray) {
    val temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

/**
 * 32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
 */
fun _0032_longestValidParentheses() {
    println("--------_0032_longestValidParentheses-------")
    println(longestValidParentheses("(()"))
    println(longestValidParentheses(")()())"))
    println(longestValidParentheses("(()()())"))
    println(longestValidParentheses("()()())"))
    println(longestValidParentheses("(()()()"))
}

/**
借助栈来求解，需要定义个 start 变量来记录合法括号串的起始位置，遍历字符串，
如果遇到左括号，则将当前下标压入栈，
如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到 start，
如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和 i - start + 1 中的较大值，
否则更新结果和 i - st.peek() 中的较大值
 */
fun longestValidParentheses(s: String): Int {
    var res = 0;
    var start = 0;
    val st = Stack<Int>()
    for (i in s.indices) {
        if (s[i] == '(') {
            st.push(i)
        } else if (s[i] == ')') {
            if (st.empty()) {
                start = i + 1
            } else {
                st.pop()
                res = if (st.empty()) Math.max(res, i - start + 1) else Math.max(res, i - st.peek())
            }
        }
    }
    return res
}

/**
 * 33. 搜索旋转排序数组
给你一个整数数组 nums ，和一个整数 target 。
该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4
 */
fun _0033_search() {
    println("--------_0033_search-------")
    println(search(intArrayOf(4, 5, 6, 7, 0, 1, 2), 0))
    println(search(intArrayOf(4, 5, 6, 7, 0, 1, 2), 3))
    println(search(intArrayOf(1), 0))
    println(search(intArrayOf(3, 1), 1))
    println(search(intArrayOf(3, 1), 3))
}

/**
二分搜索法的关键在于获得了中间数后，判断下面要搜索左半段还是右半段,
如果中间的数小于最右边的数，则右半段是有序的，
若中间数大于最右边数，则左半段是有序的，
我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了
 */
fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        if (nums[mid] == target)
            return mid
        if (nums[mid] < nums[right]) {
            if (nums[mid] < target && nums[right] >= target)
                left = mid + 1
            else
                right = mid - 1
        } else {
            if (nums[left] <= target && nums[mid] > target)
                right = mid - 1
            else
                left = mid + 1
        }
    }
    return -1
}

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
 */
fun _0034_searchRange() {
    println("--------_0034_searchRange-------")
    println(searchRange(intArrayOf(5, 7, 7, 8, 8, 10), 10).contentToString())
    println(searchRange(intArrayOf(5, 7, 7, 8, 8, 10), 9).contentToString())
    println(searchRange(intArrayOf(5, 7, 7, 8, 8, 10), 8).contentToString())
    println(searchRange(intArrayOf(5, 7, 7, 8, 8, 10), 7).contentToString())
    println(searchRange(intArrayOf(5, 7, 7, 8, 8, 10), 6).contentToString())
    println(searchRange(intArrayOf(5, 7, 7, 8, 8, 10), 5).contentToString())
}

/**
因为给的是按照升序排列的整数数组，使用两次二分查找法，第一次找到左边界，第二次调用找到右边界即可
 */
fun searchRange(nums: IntArray, target: Int): IntArray {
    val res = intArrayOf(-1, -1)
    var left = 0
    var right = nums.size
    while (left < right) {
        val mid = left + (right - left) / 2
        if (nums[mid] < target)
            left = mid + 1
        else
            right = mid
    }
    if (right == nums.size || nums[right] != target)
        return res
    res[0] = right
    right = nums.size
    while (left < right) {
        val mid = left + (right - left) / 2
        if (nums[mid] <= target)
            left = mid + 1
        else
            right = mid
    }
    res[1] = right - 1
    return res
}

/**
 * 35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
 */
fun _0035_searchInsert() {
    println("--------_0035_searchInsert-------")
    println(searchInsert(intArrayOf(1, 3, 5, 6), 5))
    println(searchInsert(intArrayOf(1, 3, 5, 6), 2))
    println(searchInsert(intArrayOf(1, 3, 5, 6), 7))
    println(searchInsert(intArrayOf(1, 3, 5, 6), 0))
}

/**
只需要遍历一遍原数组，若当前数字大于或等于目标值，则返回当前坐标，
如果遍历结束了，说明目标值比数组中任何一个数都要大，则返回数组长度n即可
可以用二分搜索法来优化时间复杂度
 */
fun searchInsert(nums: IntArray, target: Int): Int {
    if (nums.last() < target) return nums.size
    var left = 0
    var right = nums.size
    while (left < right) {
        val mid = left + (right - left) / 2
        if (nums[mid] < target)
            left = mid + 1
        else
            right = mid
    }
    return right
}

/**
 *36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:
输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。
 */
fun _0036_isValidSudoku() {
    println("--------_0036_isValidSudoku-------")
    println(
        isValidSudoku(
            arrayOf(
                charArrayOf('8', '3', '.', '.', '7', '.', '.', '.', '.'),
                charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
                charArrayOf('.', '9', '5', '.', '.', '.', '.', '6', '.'),
                charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
                charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
                charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
                charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
                charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
                charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9'),
            )
        )
    )
    println(
        isValidSudoku(
            arrayOf(
                charArrayOf('8', '3', '.', '.', '7', '.', '.', '.', '.'),
                charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
                charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
                charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
                charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
                charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
                charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
                charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
                charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9'),
            )
        )
    )
}

/**
想必数独游戏我们都玩过，就是给一个 9x9 大小的矩阵，可以分为9个 3x3 大小的矩阵，
要求是每个小矩阵内必须都是1到9的数字不能有重复，同时大矩阵的横纵列也不能有重复数字
在遍历每个数字的时候，就看看包含当前位置的行和列以及 3x3 小方阵中是否已经出现该数字，
这里需要三个 boolean 型矩阵，大小跟原数组相同，分别记录各行，各列，各小方阵是否出现某个数字，
其中行和列标志下标很好对应，就是小方阵的下标需要稍稍转换一下
其中一维下标 n 对于3个二维数组分别表示：第 n 行，第 n 列，第 n 个子九宫格
其中二维下标 m 对于3个二维数组分别表示：在当前行、列、子九宫格的数字m
二维数组中的值则表示：该数字是否出现过
 */
fun isValidSudoku(board: Array<CharArray>): Boolean {
    val rows = Array(9) { BooleanArray(9) }
    val cols = Array(9) { BooleanArray(9) }
    val boxs = Array(9) { BooleanArray(9) }
    for (i in board.indices) {
        for (j in board[i].indices) {
            if (board[i][j] != '.') {
                val num = board[i][j] - '0' - 1
                val k = i / 3 * 3 + j / 3
                if (rows[i][num] || cols[j][num] || boxs[k][num]) return false
                rows[i][num] = cols[j][num]
                cols[j][num] = boxs[k][num]
                boxs[k][num] = true
            }
        }
    }
    return true
}

/**
 * 37. 解数独
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
提示：
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
 */
fun _0037_solveSudoku() {
    println("--------_0037_solveSudoku-------")
    solveSudoku(
        arrayOf(
            charArrayOf('5', '3', '.', '.', '7', '.', '.', '.', '.'),
            charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
            charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
            charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
            charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
            charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
            charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
            charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
            charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9'),
        )
    )
}

fun solveSudoku(board: Array<CharArray>) {
    helper(board)
    for (cs in board) {
        println(cs.contentToString())
    }
}

fun helper(board: Array<CharArray>): Boolean {
    for (i in board.indices) {
        for (j in board[i].indices) {
            if (board[i][j] != '.') continue
            for (c in '1'..'9') {
                if (!isValidSK(board, i, j, c)) continue
                board[i][j] = c
                if (helper(board)) return true
                board[i][j] = '.'
            }
            return false
        }
    }
    return true
}

fun isValidSK(board: Array<CharArray>, i: Int, j: Int, c: Char): Boolean {
    for (k in 0..8) {
        if (board[k][j] != '.' && board[k][j] == c) return false
        if (board[i][k] != '.' && board[i][k] == c) return false
        val row = i / 3 * 3 + k / 3
        val col = j / 3 * 3 + k % 3
        if (board[row][col] != '.' && board[row][col] == c) return false
    }
    return true
}

/**
 * 38. 外观数列
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。
然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。
要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
示例 1：
输入：n = 1
输出："1"
解释：这是一个基本样例。
示例 2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示：
1 <= n <= 30
 */
fun _0038_countAndSay() {
    println("--------_0038_countAndSay-------")
    println(countAndSay(1))
    println(countAndSay(2))
    println(countAndSay(3))
    println(countAndSay(4))
    println(countAndSay(5))
    println(countAndSay(6))
    println(countAndSay(7))
    println(countAndSay(8))
    println(countAndSay(9))
}

/**
对于前一个数，找出相同元素的个数，把个数和该元素存到新的 string 里
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
 */
fun countAndSay(n: Int): String {
    println("countAndSay_$n:")
    if (n <= 0) return ""
    var res = "1"
    var n = n
    while (--n > 0) {
        var cur = ""
        var i = 0
        while (i < res.length) {
            var cnt = 1
            while (i + 1 < res.length && res[i] == res[i + 1]) {
                ++cnt
                ++i
            }
            cur += cnt.toString() + res[i]
            i++
        }
        res = cur
    }
    return res
}

/**
 * 39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
 */
fun _0039_combinationSum() {
    println("--------_0039_combinationSum-------")
    println(combinationSum(intArrayOf(2, 3, 6, 7), 7))
    println(combinationSum(intArrayOf(2, 3, 5), 8))
}

/**
在一个函数中完成递归，要先给数组排序，然后遍历，如果当前数字大于 target，说明肯定无法组成 target，
由于排过序，之后的也无法组成 target，直接 break 掉。如果当前数字正好等于 target，则当前单个数字就是一个解，
组成一个数组然后放到结果 res 中。然后将当前位置之后的数组取出来，调用递归函数，注意此时的 target 要减去当前的数字，
然后遍历递归结果返回的二维数组，将当前数字加到每一个数组最前面，然后再将每个数组加入结果 res 即可
 */
fun combinationSum(candidates: IntArray, target: Int): ArrayList<ArrayList<Int>> {
    Arrays.sort(candidates)
    val res = ArrayList<ArrayList<Int>>();
    for (i in candidates.indices) {
        if (candidates[i] > target) break
        if (candidates[i] == target) {
            res.add(arrayListOf(candidates[i]))
            break
        }
        val vec = candidates.copyOfRange(i, candidates.size)
        val tmp = combinationSum(vec, target - candidates[i])
        for (a in tmp) {
            a.add(0, candidates[i])
            res.add(a)
        }
    }
    return res
}

/**
 * 40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]
 */
fun _0040_combinationSum2() {
    println("--------_0040_combinationSum2-------")
    println(combinationSum2(intArrayOf(10, 1, 2, 7, 6, 1, 5), 8))
    println(combinationSum2(intArrayOf(2, 5, 2, 1, 2), 5))
}

/**
 * 与上题类似，只是candidates 中的每个数字在每个组合中只能使用一次
 * 所以在获取vec时，将i换成i+1即可，即用过i，则从i的下一个开始递归
 */
fun combinationSum2(candidates: IntArray, target: Int): ArrayList<ArrayList<Int>> {
    Arrays.sort(candidates)
    val res = ArrayList<ArrayList<Int>>();
    for (i in candidates.indices) {
        if (i > 0 && candidates[i] == candidates[i - 1]) continue
        if (candidates[i] > target) break
        if (candidates[i] == target) {
            res.add(arrayListOf(candidates[i]))
            break
        }
        val vec = candidates.copyOfRange(i + 1, candidates.size)
        val tmp = combinationSum2(vec, target - candidates[i])
        for (a in tmp) {
            a.add(0, candidates[i])
            res.add(a)
        }
    }
    return res
}

/**
 * 41. 缺失的第一个正数
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
 */
fun _0041_firstMissingPositive() {
    println("--------_0041_firstMissingPositive-------")
    println(firstMissingPositive(intArrayOf(1, 2, 0)))
    println(firstMissingPositive(intArrayOf(3, 4, -1, 1)))
    println(firstMissingPositive(intArrayOf(7, 8, 9, 11, 12)))
}

/**
需要把 nums[i] 放在 nums[nums[i] - 1]上，遍历整个数组，如果 nums[i] != i + 1, 而 nums[i] 为整数且不大于n，
另外 nums[i] 不等于 nums[nums[i] - 1] 的话，将两者位置调换，如果不满足上述条件直接跳过，
最后再遍历一遍数组，如果对应位置上的数不正确则返回正确的数
 */
fun firstMissingPositive(nums: IntArray): Int {
    val n = nums.size
    for (i in nums.indices) {
        while (nums[i] in 1..n && nums[nums[i] - 1] != nums[i]) {
            swap(i, nums[i] - 1, nums)
        }
    }
    for (i in nums.indices) {
        if (nums[i] != i + 1)
            return i + 1
    }
    return n + 1
}

/**
 * 42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1:
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
 */
fun _0042_trap() {
    println("--------_0042_trap-------")
    println(trap(intArrayOf(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))
    println(trap(intArrayOf(4, 2, 0, 3, 2, 5)))
}

/**
 * 只需要遍历一次, 需要 left 和 right 两个指针分别指向数组的首尾位置，从两边向中间扫描，
 * 在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是 left 指向的值，则从左向右扫描，
 * 如果较小值是 right 指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，
 * 如遇到的值大，则重新确定新的窗口范围，以此类推直至 left 和 right 指针重合
 */
fun trap(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var level = 0
    var res = 0
    while (left < right) {
        val lower = height[if (height[left] < height[right]) left++ else right--]
        level = Math.max(level, lower)
        res += level - lower
    }
    return res
}

/**
 * 43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
 */
fun _0043_multiply() {
    println("--------_0043_multiply-------")
    println(multiply("2", "3"))
    println(multiply("8", "22"))
    println(multiply("123", "456"))
}

/**
由于要从个位上开始相乘，所以从 num1 和 num2 字符串的尾部开始往前遍历，分别提取出对应位置上的字符，将其转为整型后相乘。
然后确定相乘后的两位数所在的位置 p1 和 p2，由于 p2 相较于 p1 是低位，所以将得到的两位数 mul 先加到 p2 位置上去，
这样可能会导致 p2 位上的数字大于9，所以将十位上的数字要加到高位 p1 上去，只将余数留在 p2 位置，这样每个位上的数字都变成一位。
然后要做的是从高位开始，将数字存入结果 res 中，记住 leading zeros 要跳过，
最后处理下 corner case，即若结果 res 为空，则返回 "0"，否则返回结果 res
 */
fun multiply(num1: String, num2: String): String {
    var res = StringBuffer()
    val m = num1.length
    val n = num2.length
    val vals = IntArray(m + n)
    for (i in m - 1 downTo 0) {
        for (j in n - 1 downTo 0) {
            val mul = (num1[i] - '0') * (num2[j] - '0')
            val p1 = i + j
            val p2 = i + j + 1
            val sum = mul + vals[p2]
            vals[p1] += sum / 10
            vals[p2] = sum % 10
        }
    }
    for (v in vals) {
        if (res.isNotEmpty() || v != 0)
            res.append((v))
    }
    return if (res.isEmpty()) "0" else res.toString()
}

/**
 * 44. 通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false
 */
fun _0044_isMatch() {
    println("--------_0044_isMatch-------")
    println(isMatch1("aa", "a"))
    println(isMatch1("aa", "*"))
    println(isMatch1("cb", "?a"))
    println(isMatch1("adceb", "*a*b"))
    println(isMatch1("acdcb", "a*c?b"))
}

fun isMatch1(s: String, p: String): Boolean {
    var i = 0
    var j = 0
    var iStar = -1
    var jStar = -1
    val m = s.length
    val n = p.length
    while (i < m) {
        if (j < n && (s[i] == p[j] || p[j] == '?')) {
            ++i
            ++j
        } else if (j < n && p[j] == '*') {
            iStar = i
            jStar = j++
        } else if (iStar >= 0) {
            i = ++iStar
            j = jStar + 1
        } else return false
    }
    while (j < n && p[j] == '*')
        ++j
    return j == n
}

/**
 * 45. 跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
 */
fun _0045_jump() {
    println("--------_0045_jump-------")
    println(jump(intArrayOf(2, 3, 1, 1, 4)))
}

/**
cur 是当前能到达的最远位置，last 是上一步能到达的最远位置，遍历数组，首先用 i + nums[i] 更新 cur，
然后判断如果当前位置到达了 last，即上一步能到达的最远位置，说明需要再跳一次了，将 last 赋值为 cur，
并且步数 res 自增1，这里小优化一下，判断如果 cur 到达末尾了，直接 break 掉即可
 */
fun jump(nums: IntArray): Int {
    var res = 0
    val n = nums.size
    var last = 0
    var cur = 0
    for (i in nums.indices) {
        cur = Math.max(cur, i + nums[i])
        if (i == last) {
            last = cur
            ++res
            if (cur >= n - 1) break
        }
    }
    return res
}

/**
 * 46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
 */
fun _0046_permute() {
    println("--------_0046_permute-------")
    println(permute(intArrayOf(1, 2, 3)))
}

/**
当 n=1 时，数组中只有一个数 a1，其全排列只有一种，即为 a1
当 n=2 时，数组中此时有 a1a2，其全排列有两种，a1a2 和 a2a1，
那么此时考虑和上面那种情况的关系，可以发现，其实就是在 a1 的前后两个位置分别加入了 a2
当 n=3 时，数组中有 a1a2a3，此时全排列有六种，分别为 a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。
那么根据上面的结论，实际上是在 a1a2 和 a2a1 的基础上在不同的位置上加入 a3 而得到的。
 */
fun permute(nums: IntArray): List<List<Int>> {
    val res = LinkedList<List<Int>>()
    res.add(ArrayList())
    for (i in nums) {
        for (k in res.size downTo 1) {
            val item = res.pollFirst() //每次取出来一个并且弹出
            for (j in 0..item.size) {
                val temp: ArrayList<Int> = ArrayList(item)
                temp.add(j, i)
                res.add(temp)
            }
        }
    }
    return res
}

/**
 * 47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
 */
fun _0047_permuteUnique() {
    println("--------_0047_permuteUnique-------")
    println(permuteUnique(intArrayOf(1, 1, 2)))
    println(permuteUnique(intArrayOf(1, 2, 3)))
}

fun permuteUnique(nums: IntArray): List<List<Int>> {
    val res = ArrayList<List<Int>>()
    Arrays.sort(nums)
    permute2(nums, 0, res)
    return res
}

fun permute2(nums: IntArray, start: Int, res: java.util.ArrayList<List<Int>>) {
    if (start >= nums.size) res.add(nums.toList())
    for (i in start until nums.size) {
        var j = i - 1
        while (j >= start && nums[j] != nums[i]) --j
        if (j != start - 1) continue
        swap(i, start, nums)
        permute2(nums, start + 1, res)
        swap(i, start, nums)
    }
}


/**
 * 49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
 */
fun _0049_groupAnagrams() {
    println("--------_0049_groupAnagrams-------")
    val res = groupAnagrams(arrayOf("eat", "tea", "tan", "ate", "nat", "bat"))
    println(res)
}

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val res = ArrayList<ArrayList<String>>()
    val map = HashMap<String, Int>()
    for (s in strs) {
        val arr = s.toCharArray()
        Arrays.sort(arr)
        var temp = ""
        for (c in arr) {
            temp += c.toString()
        }
        if (!map.containsKey(temp)) {
            map[temp] = res.size
            res.add(ArrayList())
        }
        res[map[temp]!!].add(s)
    }
    return res
}

/**
 * 50. Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
 */
fun _0050_myPow() {
    println("--------_0050_myPow-------")
    println(myPow(2.0, 10))
    println(myPow(2.1, 3))
    println(myPow(2.0, -2))
}

fun myPow(x: Double, n: Int): Double {
    if (n == 0) return 1.0
    if (n == Int.MIN_VALUE) return 1 / x * myPow(x, n + 1)
    if (n < 0) return 1 / myPow(x, -n)
    val y = myPow(x, n / 2)
    return if (n % 2 == 0) y * y else x * y * y
}



fun main() {
    test_1_50()
}


private fun test_1_50() {
    _0001_twoSum1()
    _0002_addTwoNumbers()
    _0003_lengthOfLongestSubstring1()
    _0004_findMedianSortedArrays()
    _0005_longestPalindrome()
    _0006_convert()
    _0007_reverse()
    _0008_myAtoi()
    _0009_isPalindrome()
    _0010_isMatch()
    _0011_maxArea()
    _0012_intToRoman()
    _0013_romanToInt()
    _0014_longestCommonPrefix()
    _0015_threeSum()
    _0016_threeSumClosest()
    _0017_letterCombinations()
    _0018_fourSum()
    _0019_removeNthFromEnd()
    _0020_isValid()
    _0021_mergeTwoLists1()
    _0022_generateParenthesis()
    _0023_mergeKLists()
    _0024_swapPairs()
    _0025_reverseKGroup1()
    _0026_removeDuplicates()
    _0027_removeElement()
    _0028_strStr()
    _0029_divide()
    _0030_findSubstring()
    _0031_nextPermutation()
    _0032_longestValidParentheses()
    _0033_search()
    _0034_searchRange()
    _0035_searchInsert()
    _0036_isValidSudoku()
    _0037_solveSudoku()
    _0038_countAndSay()
    _0039_combinationSum()
    _0040_combinationSum2()
    _0041_firstMissingPositive()
    _0042_trap()
    _0043_multiply()
    _0044_isMatch()
    _0045_jump()
    _0046_permute()
    _0047_permuteUnique()
    _0048_rotate()
    _0049_groupAnagrams()
    _0050_myPow()
}